Theo Shaun Considine, điều phối viên phát hành của hãng Columbia Records vào năm 1965, "Like a Rolling Stone" ban đầu bị xếp vào danh sách "hủy bỏ phát hành" vì mối lo của bộ phận bán hàng và tiếp thị đối với độ dài 6 phút chưa từng có của một ca khúc với cái giọng hát rock khàn khàn. Những ngày tiếp theo, Considine mang đĩa bài hát này đến một câu lạc bộ mang tên Arthur - một câu lạc bộ mới mở và nổi tiếng với giới tiệc tùng và truyền thông.[1][24] Theo sự khẳng định của đám đông, bản demo này được phát đi phát lại, cho đến khi buổi tiệc kết thúc. Sáng hôm sau, một DJ và đạo diễn chương trình xếp hạng top 40 ca khúc trong thành phố của đài phát thanh mang tên Columbia yêu cầu cung cấp bản sao.[1] Không lâu sau, vào ngày 20 tháng 7 năm 1965, "Like a Rolling Stone" đã được phát hành dưới dạng đĩa đơn cùng với "Gates of Eden" ở mặt B.[25][26][27]

Mặc dù với độ dài hơn 6 phút, ca khúc đã trở thành hit lớn nhất của Dylan cho đến ngày hôm nay.[21][28] và trụ vững trên bảng xếp hạng Mỹ 12 tuần, đạt vị trí thứ 2 trên bảng xếp hạng chỉ sau hit của The Beatles là "Help!".[29][30] Các bản sao quảng bá phát hành bởi các DJ vào ngày 15 tháng 6 chỉ gồm 2 đoạn và 2 lần lặp lại điệp khúc trong một mặt đĩa, trong khi phần giang tấu của ca khúc lại bị ghép vào mặt kia của đĩa. Các DJ muốn chơi toàn bộ bài hát vì như thế sẽ không phải phụ thuộc vào mặt đĩa.[31][32] Trong khi đó một số đài phát thành lại rất miễn cưỡng khi phát ca khúc một cách đầy đủ, rốt cuộc lại bị khán giả yêu cầu bắt buộc phát cả bài.[27][33] Chính nhờ vậy mà đĩa đơn đạt vị trí số 2 chỉ vài tuần sau khi phát hành.[33] Ca khúc cũng nằm trong Top 10 ở các nước khác bao gồm Canada, Ireland, Hà Lan, và Anh.[34][35][36][37]